package codeTop;

import javax.swing.plaf.basic.BasicIconFactory;
import java.util.Arrays;
import java.util.Random;
import java.util.Timer;

public class q912 {
    public int[] sortArray(int[] nums) {
        mergeSort(nums,0, nums.length-1);
        return nums;
    }
    void quickSort(int[] nums,int low,int high){
        if (low < high) {
            int partition = partition(nums, low, high);
            quickSort(nums,low,partition-1);
            quickSort(nums,partition+1,high);
        }
    }
    int partition(int[] nums,int low,int high){
        Random random = new Random();
        int rand = random.nextInt(high - low + 1)+low;
        int temp = nums[low];
        nums[low] = nums[rand];
        nums[rand] = temp;
        int pivot = nums[low];
        while (low < high) {
            while (low < high&&nums[high] >= pivot) high--;
            nums[low] = nums[high];
            while (low < high&&nums[low]<=pivot) low++;
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }

    public int[] sortArrayHeap(int[] nums) {
        buildHeap(nums);
        heapSort(nums);
        return nums;
    }

    private void heapSort(int[] nums) {
        for (int i = nums.length-1; i >=0 ; i--) {
            swap(nums,i,0);
            adjustHeap(nums,0,i);
        }
    }

    private void buildHeap(int[] nums) {
        for (int i = nums.length/2-1; i >=0; i--) {
            adjustHeap(nums,i, nums.length);
        }
    }

    private void adjustHeap(int[] nums, int head,int len) {
        for (int i = head*2+1; i < len ; i = i*2+1) {
            if (i+1< len&&nums[i+1]>nums[i]){
                i = i+1;
            }
            if (nums[head]<nums[i]){
                swap(nums,head,i);
                head = i;
            }else {
                break;
            }
        }
    }
    private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    void mergeSort(int[] nums,int l,int r){
        if (l == r) {
            return;
        }
        int mid = l+(r-l)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);
        merge(nums,l,mid,mid+1,r);
    }
    void merge(int[] nums,int l1,int r1,int l2,int r2){
        int[] arr = new int[r1-l1+1+r2-l2+1];
        int idx = 0,idx1 = l1,idx2 = l2;
        while (idx1 <= r1 && idx2 <= r2) {
            if (nums[idx1]<=nums[idx2]){
                arr[idx++] = nums[idx1++];
            }else {
                arr[idx++] = nums[idx2++];
            }
        }
        while (idx1 <= r1) {
            arr[idx++] = nums[idx1++];
        }
        while (idx2 <= r2) {
            arr[idx++] = nums[idx2++];
        }
        idx = 0;
        for (int num : arr) {
            nums[l1+idx++] = num;
        }
    }


    public static void main(String[] args) {
        q912 q = new q912();
        System.out.println(Arrays.toString(q.sortArray(new int[]{5, 2, 3, 1})));
    }
}
